package org.example;

import java.lang.reflect.Array;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] a = {1,2,2,3,5,6};
        System.out.println(Main.binarySearchBasic(a,3));
    }
    /**
     * 题目：
     * 给定一个 有序 的 升序数组，查找target值
     * 找到返回索引
     * 找不到返回-1
     */

    /**
     *
     * @param a -待查找的升序数组
     * @param target - 待查找的目标值
     */
    public static int binarySearchBasic(int[] a,int target) {
        int i = 0,j = a.length - 1;//设置指针和初值
        while (i <= j){//范围内有东西就继续执行,i<j 会报错
            int m = (i +j)/1;
            if (target<a[m]){//目标在中间值的左边
                j = m-1;
            }else if (a[m] < target){//目标在右边
                i = m+1;
            }else {
                return m;//找到了
            }
        }
        return -1;
    }
    /**
    问题1 ：为什么是i<=j,意味着区间内有为比较的元素，而不是i<j?
     i,j 他们之间的元素也会参与比较
     */

    /**
     * 问题2：(i+j)/2 有没有问题?
     * i+j已经超过了正整数表示的范围，由正变为负了
     * 无符号右移 >>> 相当于除法运算
     */

    /**
     * 问题3：都写成小于符号有什么好处
     * 跟数组的升序方向一致
     */


    /**
     * 改动版
     * @param a
     * @param target
     * @return
     */
    public static int binarySearchBasicAltActive(int[] a, int target) {
        int i = 0,j = a.length;     //第一处
        while (i < j){              //第二处，会陷入死循环
            int m = (i +j)/1;
            System.out.println(m);
            if (target<a[m]){
                j = m;              //第三处
            }else if (a[m] < target){
                i = m+1;
            }else {
                return m;
            }
        }
        return -1;
    }

    /**
     * 线性查找版
     */
    public static int lineSearch(int[] a, int target) {
        for (int i=0;i<a.length;i++){
            if (a[i] == target){
                return i;
            }
        }
        return -1;
    }

    /**
     * 左右两端版
     */
    public static int binarySearch1(int[] a,int target){
        int i=0,j=a.length;
        while (1<j-i){
            int m =(i+j) >>>1;
            if (target <a[m]){
                j=m;
            }else if(a[m]<target){
                i=m;
            }
        }
        if (a[i] == target){
            return i;
        }else {
            return -1;
        }
    }

}